package EP::Visualization::TreeGraphic;

use strict;

use EP::Visualization::Graphics;
use EP::Visualization::Hooks;

use GD;

use PDL;
use PDL::NiceSlice;

use Data::UUID;

our @ISA = qw ( EP::Visualization::Graphics );

#######################################################
# This method sets the data and already calculates the #
# position of the leaves in the final tree            # 
#######################################################
sub setData {
  my $self = shift;
  my %params = @_;

  die "No tree supplied to TreeGraphic::setData" if not $params{data};

  $self->{leaf_height} = $params{leaf_height};
  $self->{tree_width} = $params{tree_width} || 300;
  $self->{cutpoints} = $params{cutpoints};
  $self->{minitree} = $params{minitree} || 0;

  $self->read_in_tree ( $params{data} );
  $self->_reorder_tree ( $params{reorder} ) if exists $params{reorder};
  $self->update();

  return;
}

# Sub: reorder_tree
#   Tries to impose an ordering on the tree by supplying a different ordered list of ID's. If this ordering breaks the
#   tree structure, it will throw an error.
sub reorder_tree {
  my $self = shift;
  my ( $neworder ) = @_;

  $self->_reorder_tree ( $neworder );
  $self->update();
}

# Sub: _reorder_tree
#   Internal sub to do the tree reordering (See: reorder_tree).
sub _reorder_tree {
  my $self = shift;
  my ($neworder) = @_;

  my $order = 1 + pdl $self->treewalk();
  my @TREE_R = @{$self->{TREE_R}};
  my @TREE_L = @{$self->{TREE_L}};

  foreach ( sort { $self->{DIST}{$a} <=> $self->{DIST}{$b} } keys %{$self->{DIST}} ) {
    my ($l, $r) = split /:/, $_;

    my $wlo = which ( $order == $l );
    my $wro = which ( $order == $r );

    my $wln = which ( $neworder == $l );
    my $wrn = which ( $neworder == $r );

    if ( ( $wlo - $wro ) * ( $wln - $wrn ) < 0 ) {
      # swap in tree
      my $N = $self->{SUBTREE}{$_};
      ( $TREE_L[$N] , $TREE_R[$N] ) = ( $TREE_R[$N] , $TREE_L[$N] );

      # swap in $order
      $order($wlo) .= $r;
      $order($wro) .= $l;
    }
  }

  $self->{TREE_R} = \@TREE_R;
  $self->{TREE_L} = \@TREE_L;
}

# Sub: update
#   Updates the data of the object, is used when collapsing trees. If no new data object is passed, just reinitializes the ordering/hooks.
sub update {
  my $self = shift;
  my $newdata = shift;

  $self->read_in_tree ( $newdata ) if $newdata;

  warn "Update: walking the tree...";
  my @order = $self->treewalk();

  my $hook = new EP::Visualization::Hooks ( \@order );
  $self->setHook ( $hook );
}

#################################################
#returns string identifying the object as a tree#
#################################################
sub getType {
  return "tree";
}

#################################################
#set the orientation of the tree                #
#################################################

sub setOrientation {
  my $self = shift;
  my $orientation = shift;
  $self ->{ orientation } = $orientation;
  if ( $orientation == -90 ){
    my @hook = @{ $self -> getHook -> getHookSet() };
    @hook = reverse @hook;
    my $hook = new EP::Visualization::Hooks( \@hook );
    $self -> setHook( $hook );
  }
  return;
}

#####################################################
#set the hook                                       #
#####################################################

sub setHook {
  my $self = shift;
  my $hook= shift;
  $self -> { hook } = $hook;
  return;
}

#####################################################
#get the hook                                       #
#####################################################

sub getHook{
  my $self = shift;
  return $self -> { hook };
}

sub getWidth {
  my $self = shift;

  return $self->{tree_width} if $self->getOrientation() != 0;
  return $self->{nr_leaves} * $self->{'leaf_height'};
}

sub getHeight {
  my $self = shift;

  return $self->{nr_leaves} * $self->{'leaf_height'} if $self->getOrientation() != 0;
  return $self->{tree_width};
}

sub to_png {
  my $self = shift;
  my ( $png, $height, $width, $xposition, $yposition ) = @_;

  ( $width, $height ) = ( $height, $width ) if $self->getOrientation() == 0;
  my $gd_tree = $self->draw_png_tree ( $width, $height, $self->{leaf_height} );

  if ( $self->getOrientation() == 0 ) {
    ( $width, $height ) = ( $height, $width );
    $gd_tree = $gd_tree->copyRotate270();
  }

  $png->copy ( $gd_tree, $xposition, $yposition, 0, 0, $width, $height );

  return $png;
}

# Sub: to_svg
#   Produces the SVG elements of this object.
sub to_svg {
  my $self = shift;
  my ( $svg, $height, $width, $xposition, $yposition ) = @_;
  my $leafUnit = $self->{leaf_height};

  my @data  = @{ $self->getData() };
  my @order = @{ $self->getHook->getHookSet() };

  my $space;
  my %leafPos;                                         #this hash will return the position of a leaf given the hook id
  my %leafNode;                                        #hash that stores to which current node the leaves are attached
  my @nodeXpos;                                        #array that stores for each node it's x position
  my @nodeYpos;                                        #array that stores for each node it's y position
  my %leaf;                                            #this hash returns a boolean given the hook id. the boolean is 1
  my $rotate = $self->getOrientation();              #if the leaf has not yet been connected to a first node
  my $group;
  my $maxDist = 0;
  my $minDist = 1;

  my $tree_id = $self->get_uuid();

  local ($^W) = 0;

  # if the tree is rotated, the height becomes width and the width height as tree are always drawn like a top tree of a heatmap and then rotated 
  if ( $rotate == 90 ) {
    my $newWidth = $height;
    $height      = $width - 8;
    $width       = $newWidth;
    $space       = $leafUnit / 2;
    my ($xtrans, $ytrans) = ( $yposition, -($xposition + $height + 8) );

    $group       = $svg->group ( id => $tree_id, transform => "rotate($rotate) translate($xtrans,$ytrans)" );
  } elsif ( $rotate == -90 ) {
    my $newWidth = $height;
    $height      = $width - 8;
    $width       = $newWidth;
    $space       = $leafUnit / 2;
    my ($xtrans, $ytrans)   = ( -($width + $yposition), $xposition );

    $group       = $svg->group ( id => $tree_id, transform => "rotate($rotate) translate($xtrans,$ytrans)" );
  } elsif ( $rotate == 180 ) {
    $space       = $leafUnit / 2;
    my ($xtrans, $ytrans) = ( -($xposition + $width), -($yposition + $height) );
    $height      = $height - 4;

    $group       = $svg->group ( id => $tree_id, transform => "rotate($rotate) translate($xtrans,$ytrans)" );
  } else {
    $height      = $height - 8;
    $space       = $leafUnit / 2;

    $group       = $svg->group ( id => $tree_id, transform => "translate($xposition,$yposition)" );
  }

  #from the hooks we can already determine the position of the leaves these are used to build up the tree upon
  for ( my $j = 0 ; $j < scalar ( @order ) ; $j++ ) {
    $leafPos{ $order[ $j ] } = $space + ( $j * $leafUnit );
    $leaf{ $order[ $j ] } = 1;
  }

  #now we add the nodes acoording to the data
  my $startdata = 0;

  if ( $#data > 200 ) {
    $startdata = $#data - 0.15 * $#data;
  }

  for my $y ( $startdata .. $#data ) {
    my $i = $#data - $y;
    my $leaf1 = $data[$i][0] - 1;
    my $leaf2 = $data[$i][1] - 1;
    my $stillLeaf1 = $leaf{$leaf1};
    my $stillLeaf2 = $leaf{$leaf2};
    my $nodeHeight = $height - ( $height * $data[$i][4] );

    my ( $v1x1, $v1x2, $v1y1, $v1y2 );
    my ( $v2x1, $v2x2, $v2y1, $v2y2 );
    my ( $hx1, $hx2, $hy1, $hy2 );

    my ( $lh1, $rh1, $lh2, $rh2 );

    if ( $stillLeaf1 & $stillLeaf2 ) { # both leaves are not yet connected to a node
      my $x1 = $leafPos{$leaf1}; # so we can use the initial position of the leaves to build the tree
      my $x2 = $leafPos{$leaf2};

      ( $v1x1, $v1x2, $v1y1, $v1y2 ) = ( $x1, $x1, $nodeHeight, $height );
      ( $v2x1, $v2x2, $v2y1, $v2y2 ) = ( $x2, $x2, $nodeHeight, $height );
      ( $hx1,  $hx2,  $hy1,  $hy2  ) = ( $x1, $x2, $nodeHeight, $nodeHeight );

      $leaf{$leaf1}     = 0;	# to indicate the leaves are now connected to a node
      $leaf{$leaf2}     = 0;
      $leafNode{$leaf1} = $y;
      $leafNode{$leaf2} = $y;

      $nodeXpos[$y] = ( abs ( $x1 - $x2 ) / 2 ) + (( $x1 >= $x2 ) ? $x2 : $x1);
      $nodeYpos[$y] = $height - ( $height * $data[$i][4] );
    } elsif ( $stillLeaf1 ) {	# only the 1st leaf is still a true leaf so here we have to connect a leaf to a node
      my $x1 = $leafPos{$leaf1};
      my $x2 = $nodeXpos[$leafNode{$leaf2}];
      my $y2 = $nodeYpos[$leafNode{$leaf2}];

      ( $v1x1, $v1x2, $v1y1, $v1y2 ) = ( $x2, $x2, $nodeHeight, $y2 );
      ( $v2x1, $v2x2, $v2y1, $v2y2 ) = ( $x1, $x2, $nodeHeight, $nodeHeight );
      ( $hx1,  $hx2,  $hy1,  $hy2  ) = ( $x1, $x1, $nodeHeight, $height );

      $leaf{$leaf1}     = 0;
      $leafNode{$leaf1} = $y;
      $leafNode{$leaf2} = $y;

      $nodeXpos[$y] = ( abs ( $x1 - $x2 ) / 2 ) + (( $x1 >= $x2 ) ? $x2 : $x1);
      $nodeYpos[$y] = $nodeHeight;
    } elsif ( $stillLeaf2 ) {                         # only the 2nd leaf is still a true leaf so here we have to connect a leaf to a node
      my $x1 = $leafPos{$leaf2};              # get x-position of the leaf
      my $x2 = $nodeXpos[$leafNode{$leaf1}];  # get x-postion of the node
      my $y2 = $nodeYpos[$leafNode{$leaf1}];  # get y-postion of the node

      ( $v1x1, $v1x2, $v1y1, $v1y2 ) = ( $x1, $x1, $nodeHeight, $height );
      ( $v2x1, $v2x2, $v2y1, $v2y2 ) = ( $x2, $x2, $nodeHeight, $y2 );
      ( $hx1,  $hx2,  $hy1,  $hy2  ) = ( $x1, $x2, $nodeHeight, $nodeHeight );

      $leaf{$leaf2}     = 0;
      $leafNode{$leaf1} = $y;
      $leafNode{$leaf2} = $y;

      $nodeXpos[$y] = ( abs ( $x1 - $x2 ) / 2 ) + (( $x1 > $x2 ) ? $x2 : $x1);
      $nodeYpos[$y] = $nodeHeight;
    } else {                                            # Both leaves are already nodes so here we connect 2 nodes
      my $x1 = $nodeXpos[$leafNode{$leaf1}];
      my $x2 = $nodeXpos[$leafNode{$leaf2}];
      my $y1 = $nodeYpos[$leafNode{$leaf1}];
      my $y2 = $nodeYpos[$leafNode{$leaf2}];

      ( $v1x1, $v1x2, $v1y1, $v1y2 ) = ( $x1, $x1, $nodeHeight, $y1 );
      ( $v2x1, $v2x2, $v2y1, $v2y2 ) = ( $x2, $x2, $nodeHeight, $y2 );
      ( $hx1,  $hx2,  $hy1,  $hy2  ) = ( $x1, $x2, $nodeHeight, $nodeHeight );

      $leafNode{$leaf1} = $y;
      $leafNode{$leaf2} = $y;

      $nodeXpos[$y] = ( abs ( $x1 - $x2 ) / 2 ) + (( $x1 > $x2 ) ? $x2 : $x1);
      $nodeYpos[$y] = $nodeHeight;
    }

    my $LH = $self->{TREE_L}->[$self->{SUBTREE}->{"$data[$i][0]:$data[$i][1]"}];
    $lh1 = $self->{ORIG_TREE}->[$self->{TREE_L}->[$LH]] || "";
    $rh1 = $self->{ORIG_TREE}->[$self->{TREE_R}->[$LH]] || "";

    my $RH = $self->{TREE_R}->[$self->{SUBTREE}->{"$data[$i][0]:$data[$i][1]"}];
    $lh2 = $self->{ORIG_TREE}->[$self->{TREE_L}->[$RH]] || "";
    $rh2 = $self->{ORIG_TREE}->[$self->{TREE_R}->[$RH]] || "";

    my @x = ( $hx2, $hx1, $v1x1, $v1x2 );
    my @y = ( $hy2, $hy1, $v1y1, $v1y2 );

    if ( !$stillLeaf1 || ( $stillLeaf1 && $stillLeaf2 ) ) {
      unshift @x, $v2x2;
      unshift @y, $v2y2;
    }

    my @points = map { int ( $x[$_]) . "," . int ($y[$_]) } 0 .. $#x;
    $group->polyline ( points => join (" ", @points),
		       id => $tree_id . ":" . $data[$i][0] . ":" . $data[$i][1],
		       lh1 => $lh1,
		       rh1 => $rh1,
		       lh2 => $lh2,
		       rh2 => $rh2,
		       leftmost  => $self->left_treewalk ( $self->{SUBTREE}->{"$data[$i][0]:$data[$i][1]"} ),
		       rightmost => $self->right_treewalk ( $self->{SUBTREE}->{"$data[$i][0]:$data[$i][1]"} ) );

  if (not $self->{minitree}){
    $group->circle ( id => $tree_id . ":" . $data[$i][0], cx => int($leafPos{$leaf1}), cy=>int($height), r=>3, style => 'fill: purple' ) if $stillLeaf1;
    $group->circle ( id => $tree_id . ":" . $data[$i][1], cx => int($leafPos{$leaf2}), cy=>int($height), r=>3, style => 'fill: purple' ) if $stillLeaf2;
		}
    foreach my $cp ( @{$self->{cutpoints}} ) {
      next if $cp > 0;
      if ($data[$i][0] == -$cp and $stillLeaf1 ) {
	$group->circle ( id => $tree_id . ":" . $data[$i][0], cx => int($leafPos{$leaf1}), cy=>int($height), r=>3, style => 'fill: red' );
      }

      if ($data[$i][1] == -$cp and $stillLeaf2) {
	$group->circle ( id => $tree_id . ":" . $data[$i][1], cx => int($leafPos{$leaf2}), cy=>int($height), r=>3, style => 'fill: red' );
      }
    }
  }
  if (not $self->{minitree}){
	# need to draw the clickie-circles afterwards, to make sure they're on top.
	for my $y ( $startdata .. $#data ) {
		my $i = $#data - $y;
		my $leftmost  = 1 + $self->left_treewalk ( $self->{SUBTREE}->{"$data[$i][0]:$data[$i][1]"} );
		my $rightmost = 1 + $self->right_treewalk ( $self->{SUBTREE}->{"$data[$i][0]:$data[$i][1]"} );
	
		$group->circle ( id => "T:$tree_id:$leftmost:$rightmost",
				onclick => "select_subtree('$tree_id', $leftmost, $rightmost, null )",
				selected => 0,
				cx => int($nodeXpos[$y]), cy=>int($nodeYpos[$y]), r=>3, class => "orangecircle",
				lh => $data[$i][0], rh => $data[$i][1] );
	}
	
	#TODO/HACK: THIS IS A VERY MESSY WAY TO FIND CUTPOINTS <-- REWRITE!!!
	for my $cp ( @{$self->{cutpoints}} ) {
	  next if $cp < 0;
	  my $m = $self->{HCLUST}->{merge}->[$cp-1];
	  foreach my $rt ( @{$self->{HCLUST}->{RTREE}} ) {
	    if ( $$rt[2] == $$m[0] and $$rt[3] == $$m[1] ) {
	      foreach my $y ( 0 .. $#data ) {
		my $i = $#data - $y;
		
		if ( $$rt[0] == $data[$i][0] and $$rt[1] == $data[$i][1] ) {
		  $group->circle ( cx => int($nodeXpos[$y]), cy=>int($nodeYpos[$y]), r=>3, style => 'fill: red' );
		}
	      }
	    }
	  }
	}
	
	$svg->script()->cdata(<<__JS__);
	getURL ( "$EP::Config::h->{CORE_HREF}/ep_get_saved_clusters.pl?tree_id=$tree_id", load_saved_clusters );
__JS__
  }
  return $svg;
}

sub draw_png_tree {
  my $self = shift;
  my ( $width, $height, $leaf_height ) = @_;

  my $tree_id = $self->get_uuid();

  my $gd_tree = new GD::Image ( $width, $height );
  my $white = $gd_tree->colorAllocate ( 255, 255, 255 );
  my $black = $gd_tree->colorAllocate ( 0, 0, 0 );

  $self->{leafnr} = 0;
  warn "Start drawing tree...";
  $self->treedraw ( 0, $gd_tree, $width, $height, $leaf_height, $black );
  warn "End drawing tree...";

  return $gd_tree;
}

sub treedraw {
  my $self = shift;
  my ( $N, $gd_tree, $width, $height, $leaf_height, $black ) = @_;

  my ( $NX, $NY, $LX, $LY, $RX, $RY, $LST, $RST, $DIS );

  if ( $self->{TREE_L}->[ $N ] == 0 ) {
    $self->{leafnr} = $self->{leafnr} + 1;
    $LY =  $self->{leafnr} * $leaf_height - int ( $leaf_height / 2 );

    return ( 0 , $LY ) ;
  }

  ( $LX, $LY ) = $self->treedraw ( $self->{TREE_L}->[ $N ], $gd_tree, $width, $height, $leaf_height, $black );
  ( $RX, $RY ) = $self->treedraw ( $self->{TREE_R}->[ $N ], $gd_tree, $width, $height, $leaf_height, $black );

  $LST = $self->{ORIG_TREE}->[$self->{TREE_L}->[$N]];
  $RST = $self->{ORIG_TREE}->[$self->{TREE_R}->[$N]];

  $DIS = $self->{DIST}->{"$LST:$RST"} ; # Distance between left and right subtrees

  my $pxDIS = int ( $DIS * ($width - 1) );

  $NX = $pxDIS;
  $NY = int ( ( $LY + $RY ) / 2 );

  $gd_tree->line ( $LX, $LY, $NX, $LY, $black );
  $gd_tree->line ( $RX, $RY, $NX, $RY, $black );
  $gd_tree->line ( $NX, $LY, $NX, $RY, $black );


  my $dist1000 = $self->{data}->[1000]->[4];
  $dist1000 = 0 if not defined $dist1000;

  return ( $NX, $NY ) if $DIS < $dist1000;

  my $leftmost  = 1;# + $self->left_treewalk  ( $self->{SUBTREE}->{"$self->{TREE_L}->[$N]:$self->{TREE_R}->[$N]"} );
  my $rightmost = 1;# + $self->right_treewalk ( $self->{SUBTREE}->{"$self->{TREE_L}->[$N]:$self->{TREE_R}->[$N]"} );

  my $orange = $gd_tree->colorResolve ( 255, 165, 0 );
  $gd_tree->filledArc ( $NX, $NY, 5, 5, 0, 360, $orange );

  my $tree_id = $self->get_uuid();

  my @c;

  if ( $self->getOrientation() == 0 ) {
    # rotate 270 about center, and shift down to match top left corner of rotated image
    my $hw = int ($width - 1) * 0.5;
    my $hh = int $height * 0.5;

    my ( $x0, $y0 ) = ($NX - $hw, $NY - $hh );
    my ( $rx, $ry ) = ( $y0, -$x0 );
    @c = ( $rx + $hw - ( $hw - $hh ), $ry + $hh - ( $hh - $hw ) );
  } else {
    @c = ($NX,$NY);
  }

  push @{$self->{image_map}}, { shape  => "circle",
				coords => "$c[0],$c[1],5",
				href   => "javascript:png_select_subtree ( $leftmost, $rightmost, $self->{ORIG_TREE}->[$self->{TREE_L}->[$N]], $self->{ORIG_TREE}->[$self->{TREE_R}->[$N]], \"$tree_id\" );" };

  return ( $NX , $NY );
}

sub to_hclust {
  my $self = shift;

  my @RTREE;
  foreach ( sort { $self->{DIST}{$a} <=> $self->{DIST}{$b} } keys %{$self->{DIST}} ) {
    my ($l, $r) = split /:/, $_;
    my $m = $self->{SUBTREE}{$_};

    my ($nl, $nr) = ( -$l, -$r );

    if ( $self->{TREE_L}->[$self->{TREE_L}->[$m]] != 0 ) {
      foreach ( my $i = $#RTREE; $i >= 0; $i-- ) {
	$nl = $i + 1 and last if $l == $RTREE[$i]->[0] or $l == $RTREE[$i]->[1];
      }
    }

    if ( $self->{TREE_L}->[$self->{TREE_R}->[$m]] != 0 ) {
      foreach ( my $i = $#RTREE; $i >= 0; $i-- ) {
	$nr = $i + 1 and last if $r == $RTREE[$i]->[1] or $r == $RTREE[$i]->[0];
      }
    }

    push @RTREE, [$l, $r, $nl, $nr, $self->{DIST}{$_}, $_];
  }

  my @merge;
  push @merge, [ @$_[2,3] ] foreach @RTREE;

  return { RTREE  => [ @RTREE ],
	   merge  => [ @merge ],
	   height => [ sort { $a <=> $b } values %{$self->{DIST}} ],
	   order  => [ map { $_ + 1 } treewalk ( $self ) ] };
}

sub read_tree_data_from_file {
  my ($file) = shift;

  my @DATA;

  open ( CLUSTER, $file ) or die "Couldn't open the hierarchical clustering file $file: $!\n";
  while (<CLUSTER>) {
    next if /^\s*#/;
    next if /^Clustering of/;

    # From the original clustering output
    my @data_row = split /\s+/;
    push @DATA, \@data_row;
  }
  close CLUSTER;

  return \@DATA;
}

sub read_in_tree {
  my $self = shift;
  my ( $tree_data ) = @_;

  my %LL;
  my @TREEDOWN;
  my $TREENODE = 0;

  my (@TREE_L, @TREE_R, %DIST, %SUBTREE, @ORIG_TREE);

  my $DATA;
  $DATA = read_tree_data_from_file ( $tree_data ) if -f $tree_data;
  $DATA = $tree_data if ref ( $tree_data ) eq "ARRAY";
  $DATA = $tree_data->{data} if ref ( $tree_data ) eq "HASH" and exists $tree_data->{data};

  die "Couldn't read in tree data $tree_data!" if not $DATA;

  my @data = @{$DATA};
  my $maxDist = 0;
  my $minDist = 1;

  #normalize data such that the distance is between 0 and 1 so drawing will occur within the borders of the object
  for ( my $a = 0; $a < scalar( @data ); $a++){
    $maxDist = $data[ $a ][ 4 ] if $data[ $a ][ 4 ] > $maxDist;
    $minDist = $data[ $a ][ 4 ] if $data[ $a ][ 4 ] < $minDist && $data[ $a ][ 4 ] != 0;
  }

  for ( my $a = 0; $a < scalar( @data ); $a++){
    $data[ $a ][ 4 ] = $minDist / 2                 if $data[ $a ][ 4 ] <= 0;
    $data[ $a ][ 4 ] = $data[ $a ][ 4 ] / $maxDist if $maxDist != 0;
  }

  foreach my $data_row ( @{$DATA} ) {
    # From the original clustering output
    my ( $LH, $RH, $LHS, $RHS, $D ) = @$data_row;

    $TREEDOWN[1] = [ 0, $LHS + $RHS ] if not exists $TREEDOWN[1];

    # @TREEDOWN  - how much space was reserved for subtree starting with that node
    my ( $TREENODE, $count ) = @{$TREEDOWN[$LH]};

    # $LHTREE, $RHTREE, $TREENODE -  tree-node id's on tree structure
    my $LHTREE = $TREENODE + 1;
    my $RHTREE = $TREENODE + nodes_in_subtree($LHS) + 1;

    ( $TREE_L   [$TREENODE], $TREE_R   [$TREENODE] ) = ( $LHTREE,           $RHTREE);
    ( $ORIG_TREE[$LHTREE  ], $ORIG_TREE[$RHTREE  ] ) = ( $LH,               $RH );
    ( $TREEDOWN [$LH      ], $TREEDOWN [$RH      ] ) = ( [ $LHTREE, $LHS ], [ $RHTREE, $RHS ] );

    $DIST{"$LH:$RH"}    = $D;
    $SUBTREE{"$LH:$RH"} = $TREENODE;

    # left leaf
    ( $TREE_L[$LHTREE], $TREE_R[$LHTREE] ) = ( 0, $LH ) if $LHS == 1;

    # right leaf
    ( $TREE_L[$RHTREE], $TREE_R[$RHTREE] ) = ( 0, $RH ) if $RHS == 1;
  }

  $self->{nr_leaves} = $$DATA[0][2] + $$DATA[0][3];
  $self->{TREE_L} = \@TREE_L;
  $self->{TREE_R} = \@TREE_R;
  $self->{DIST}   = \%DIST;
  $self->{SUBTREE} = \%SUBTREE;
  $self->{ORIG_TREE} = \@ORIG_TREE;

  $self->{data} = $DATA;
#  $self->{HCLUST} = $self->to_hclust();
}

sub nodes_in_subtree {
  my ( $leaves ) = $_[0];
  return $leaves * 2 - 1;
}

sub treewalk {
  my $self = shift;
  my ($N) = @_;

  $N = 0 if not $N;

  if ( $self->{TREE_L}->[$N] == 0 ) {
    my $leaf = $self->{TREE_R}->[$N];
    return $leaf - 1;		# subtract 1 because indices should be zero-based
  }

  return ( $self->treewalk ( $self->{TREE_L}->[$N] ),
	   $self->treewalk ( $self->{TREE_R}->[$N] ) );
}

sub left_treewalk {
  my $self = shift;
  my ($N) = @_;

  $N = 0 if not $N;

  if ( $self->{TREE_L}->[$N] == 0 ) {
    my $leaf = $self->{TREE_R}->[$N];
    return $leaf - 1;		# subtract 1 because indices should be zero-based
  }

  return ( $self->left_treewalk ( $self->{TREE_L}->[$N] ) );
}

sub right_treewalk {
  my $self = shift;
  my ($N) = @_;

  $N = 0 if not $N;

  if ( $self->{TREE_L}->[$N] == 0 ) {
    my $leaf = $self->{TREE_R}->[$N];
    return $leaf - 1;		# subtract 1 because indices should be zero-based
  }

  return ( $self->right_treewalk ( $self->{TREE_R}->[$N] ) );
}

sub tbr_buttons {
  my $self = shift;
  my $uuid = $self->get_uuid();

  return ( { id     => 'btn_save_as',
	     icon   => "$EP::Config::h->{HTML_HREF}/static/images/gui_icons/saveas.png",
	     tip    => 'Save clustering as...',
	     action => "alert('btn_saveas pressed')" },

	   { id     => 'btn_export',
	     icon   => "$EP::Config::h->{HTML_HREF}/static/images/gui_icons/save.png",
	     tip    => 'Save clusters...',
	     action => "save_clusters('$uuid')" } );
}

1;
